#ifndef CLLockFreeQueue_H
#define CLLockFreeQueue_H

template <typename T>

class CLLockFreeQueue
{
private:
	struct Node
	{
		Node(T val) : value(val), next(NULL) 
		{
		}

		T value;
		Node *next;
	};

	Node* head;		// 对应于队列的头指针
	Node* tail;     // 对应于队列的尾指针

public:

	CLLockFreeQueue()
	{
		head = new Node(T());
		tail = head;
	}

	~CLLockFreeQueue()
	{
		// release the list
		while(head != NULL)
		{
			Node* tmp = head;
			head = tmp->next;
			delete tmp;
		}
	}

	void LockFreePush(const T t)
	{
		// 设置tail->next为一个value为t的新节点
		tail->next = new Node(t);

		// 调用内存屏障防止编译器优化重排代码顺序
		asm volatile("" ::: "memory");

		// 重新设置尾节点---原子地
		(void)__sync_lock_test_and_set(&tail, tail->next);
	}

    T LockFreePop()
    {
    	T result;

    	// 队列非空
    	if(head != tail)
    	{
    		// 将head->next->value的值传给result
    		result = head->next->value;

    		// prevend compiler reordering
    		asm volatile("" ::: "memory");

    		 // 重新设置头结点---原子地
    		(void)__sync_lock_test_and_set(&head, head->next);

    		return result;
    	}

    	return NULL;
    }
};

#endif